package main

import (
	"fmt"
	"sort"
)

func main() {
	fmt.Println(subsetsWithDup([]int{1, 2, 2}))
}

func subsetsWithDup(nums []int) [][]int {
	var res [][]int
	var list []int
	var used = make(map[int]bool)
	var helper func(list []int, index int)
	sort.Ints(nums)
	helper = func(list []int, index int) {

		// 注意子集收集
		tmp := make([]int, len(list))
		copy(tmp, list)
		res = append(res, tmp)

		if index == len(nums) {
			return
		}

		for i := index; i < len(nums); i++ {
			if i > index && nums[i-1] == nums[i] && !used[i-1] {
				continue
			}
			list = append(list, nums[i])
			used[i] = true
			helper(list, i+1)
			list = list[:len(list)-1]
			used[i] = false
		}
	}
	helper(list, 0)
	return res
}
